1. Field of the Invention
Broadly speaking, this invention relates to methods and apparatus for compacting digital data. More particularly, in a preferred embodiment, this invention relates to methods and apparatus for compacting alpha-numeric data-sets, thereby significantly reducing the storage requirements for the data and improving its transmission efficiency.
2. Discussion of the Prior Art
The increased use by modern society of computers interconnected by communications and data links has led to a demand for improved, and more efficient, data transfer and storage techniques. Many of the data reduction schemes currently in use were developed to reduce the information content of television picture or other graphic information. Unfortunately, the techniques developed for such special data-sets rarely provide satisfactory results when applied to conventional alpha-numeric information. The reason for such variation in performance is that the integrity of picture information is not as readily affected by the removal of data redundancies as is alpha-numeric information. In addition, most of these data reduction schemes, which are either a form of delta modulation or the transmission of a truncated Fourier data spectrum, are not matched to the data class under consideration.
As a solution to this, and other problems, there is disclosed herein a unique digital data compaction technique which can significantly reduce data storage requirements and, in addition, greatly improve transmission efficiency. The technique of this invention examines the statistical character of a given data block, determines the optimum minimum length code for the block, and encodes (maps) the block into its most efficient code representation. The experimental application of this technique to physical data files has resulted in code bit reductions of from 40 to 60 percent of the original code requirements. While the technique presented in this invention operates on the redundancy inherent in all man-made data, it is significantly different from prior art data compression procedures. Such prior art procedures eliminate redundancy in a destructive manner and must apply data prediction techniques in order to restore the data to a reasonable estimate of its original form. The technique described herein re-encodes the data and its associated redundancy into a more efficient code without destroying the original data structure. A simple inverse mapping procedure restores the data to its original form without error. The data compaction technique of the instant invention can be both software and hardwire implemented, although only the hardwired implementation is discussed in detail. The technique of the instant invention will provide reduced data storage requirements and improved transmission efficiency in situations where user requirements do not permit the compromising of data integrity.
As previously mentioned, the technique described herein is oriented for application to alpha-numeric type data-sets, although it can also be applied to achieve coding reduction of picture information. However, when so utilized, it will not necessarily provide the minimum picture code, although it will return the picture, upon decoding, to its original quality.